﻿namespace EyeOpen.Math.Combinatorics
{
	using System;
	using System.Collections;
	using System.Collections.Generic;

	public class Combination<T> : IEnumerable<T[]>
	{
		private readonly T[] items;
		private readonly int length;

		/// <summary>
		/// Constructor for the Combination class
		/// </summary>
		/// <param name="items">Array of objects used to build combinations</param>
		/// <param name="n">Number of items in each combination</param>
		public Combination(int n, params T[] items)
		{
			this.items = items;
			length = n;
			Count = Choose(items.Length, length);
		}

		/// <summary>
		/// Number of combinations for this specific set of objects and grouping size
		/// </summary>
		public long Count { get; private set; }

		public IEnumerator<T[]> GetEnumerator()
		{
			return new CombinationEnumerator<T>(length, items);
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		/// <summary>
		/// Gets the specific lexical combination. Note that combinations are numbered from 0 to Count - 1
		/// </summary>
		/// <param name="n">Lexical combination to return</param>
		/// <returns>Array containing the nth lexical combination</returns>
		/// <exception cref="ArgumentOutOfRangeException"><c></c> is out of range.</exception>
		public T[] GetCombination(long n)
		{
			if (n >= Count)
			{
				throw new ArgumentOutOfRangeException(String.Format("Requested combination ({0}) exceeds number of combinations ({1})", n, Count));
			}

			var result = new T[length];
			var ans = new int[length];

			var a = items.Length;
			var b = length;
			var x = (Choose(a, b) - 1) - n;

			for (var i = 0; i < length; i++)
			{
				ans[i] = LargestV(a, b, x);
				x -= Choose(ans[i], b);
				a = ans[i];
				b--;
			}

			for (var i = 0; i < length; i++)
			{
				result[i] = items[items.Length - 1 - ans[i]];
			}

			return result;
		}

		// The next two methods are used to calculate the combinadic. See
		// Wikipedia article at http://en.wikipedia.org/wiki/Combinatorial_number_system
		// and the 2006 MSDN Article "Test Run" by Dr. James McCaffrey
		private int LargestV(int a, int b, long x)
		{
			var v = a - 1;
			while (Choose(v, b) > x)
			{
				v--;
			}

			return v;
		}

		/// <exception cref="ArgumentOutOfRangeException"><c>n</c> is out of range.</exception>
		private long Choose(int n, int k)
		{
			long result;

			if (n < 0)
			{
				throw new ArgumentOutOfRangeException("n", "Invalid negative parameter.");
			}

			if (k < 0)
			{
				throw new ArgumentOutOfRangeException("k", "Invalid negative parameter.");
			}

			if (n < k)
			{
				result = 0;
			}
			else if (n == k)
			{
				result = 1;
			}
			else
			{
				int delta;
				int max;
				if (k < n - k)
				{
					delta = n - k;
					max = k;
				}
				else
				{
					delta = k;
					max = n - k;
				}

				result = delta + 1;

				for (var i = 2; i <= max; i++)
				{
					checked
					{
						result = (result * (delta + i)) / i;
					}
				}
			}

			return result;
		}
	}
}